package com.example.algorithm.interview;

/**
 * 富途面试题
 *
 * @description 给定两个升序数组，找到第k大的数
 * @date 2023-12-14
 */
public class MinK {

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 4, 8, 10};
        int[] b = new int[]{2, 3, 4, 5};
        int k = 4;
        int res = findMinK(a, b, k);
        System.out.println(res);
    }

    private static int findMinK(int[] a, int[] b, int k) {
        int i = 0;
        int j = 0;
        // 此处可优化为无需引入新数组，空间复杂度O(1)
        int[] c = new int[a.length + b.length];
        for (int m = 0; m < a.length + b.length; m++) {
            if (i == a.length) {
                c[m] = b[j++];
                continue;
            }
            if (j == b.length) {
                c[m] = a[j++];
                continue;
            }
            if (a[i] < b[j]) {
                c[m] = a[i++];
            } else if (a[j] > b[j]) {
                c[m] = b[j++];
            } else {
                c[m++] = a[i++];
                c[m] = b[j++];
            }
        }
        return c[k];
    }

}
